package tree;

import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description: 113. 路径总和 II
 * User: Li_yizYa
 * Date: 2025/6/4
 * Time: 21:07
 */
public class Solution22 {
    /**
     * 递归写法
     */
    List<List<Integer>> ret = new ArrayList<>();
    List<Integer> tmp = new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return ret;
        }
        traversal(root, targetSum);
        return ret;
    }
    private void traversal(TreeNode root, int targetSum) {
        if (root == null) {
            return;
        }
        tmp.add(root.val);
        if (root.left == null && root.right == null && root.val == targetSum) {
            ret.add(new ArrayList<>(tmp));
        }
        if (root.left != null) {
            traversal(root.left, targetSum - root.val);
            tmp.remove(tmp.size() - 1);
        }
        if (root.right != null) {
            traversal(root.right, targetSum - root.val);
            tmp.remove(tmp.size() - 1);
        }
    }
}
